Algorithmie
Seconde Générale et Technologique
M-01

Algorithmie

Un algorithme est une suite finie et non ambiguë d'opérations ou d'instructions permettant de résoudre un problème ou d'obtenir un résultat. Chaque opération ou instruction est effectuée dans un ordre précis.

Les affectations

En algorithmie, l'affectation consiste à donner une valeur à une variable. En langage Python, on utilise le signe égal = pour affecter une valeur à une variable. 
a=2
b=3
a=a+b
b=a*b
  1. Quelles sont les valeurs de a et b après l'exécution de ce code ?
    Recopie et complète le tableau ci-dessous pour justifier.
Ligne n° 1 2 3 4
a ... ... ... ...
b ... ... ... ...
  1. Même consigne en échangeant les deux dernières lignes du code.
  2. Que se passe-t-il si on échange les deux premières lignes du code ?
  3. Que se passe-t-il si on échange les lignes 2 et 3 du code ?
  1. Ligne n° 1 2 3 4
    a 2 2 5 5
    b 3 3 15

    Après l'exécution de ce code, la valeur de a est 5 et la valeur de b est 15.

    2. Le script devient : 

    a=2
b=3
b=a*b
a=a+b

  2. Ligne n° 1 2 3 4
    a 2 2 2 8
    b 3 6 6

    Après l'exécution de ce code, la valeur de a est 8 et la valeur de b est 6.

  3. Le code devient : 

    b=3
a=2
a=a+b
b=a*b

    Les valeurs de a et b sont inchangées.

  4. Le code devient : 

    a=2
a=a+b
b=3
b=a*b

    Si on échange les lignes 2 et 3 du code, le code ne fonctionne plus car on ne peut pas affecter une valeur à a à la ligne 2 si b n'a pas encore été défini.

Les variables

En python, les valeurs peuvent être de différents types : int (entier), float (flottant), str (chaîne de caractères) et bool (booléen).
Opérations arithmétiques
Pour chacune des variables suivantes, indique sa valeur et son type.
  1. a=2
  2. b=5.0
  3. c=1.5+1.5
  4. c=6/3
  5. d=6.0/2
  6. e=7/4
  7. f=23//4
  8. g=23%4
  9. h=7**2
  10. i=2*2**3*5
  11. j=(2*2)**3*5
  12. k=-2**3
  1. >>> a=2
>>> a
2
>>> type(a)
<class 'int'>
  2. >>> b=5.0
>>> b
5.0
>>> type(b)
<class 'float'>
  3. >>> c=1.5+1.5
>>> c
3.0
>>> type(c)
<class 'float'>
  4. >>> c=6/3
>>> c
2.0
>>> type(c)
<class 'float'>
  5. >>> d=6.0/2
>>> d
3.0
>>> type(d)
<class 'float'>
  6. >>> e=7/4
>>> e
1.75
>>> type(e)
<class 'float'>
  7. >>> f=23//4
>>> f
5
>>> type(f)
<class 'int'>
  8. >>> g=23%4
>>> g
3
>>> type(g)
<class 'int'>
  9. >>> h=7**2
>>> h
49
>>> type(h)
<class 'int'>
  10. >>> i=2*2**3*5
>>> i
80
>>> type(i)
<class 'int'>
  11. >>> j=(2*2)**3*5
>>> j
320
>>> type(j)
<class 'int'>
  12. >>> k=-2**3
>>> k
-8
>>> type(k)
<class 'int'>
Chaînes de caractères
Pour chacune des variables suivantes, indique sa valeur et son type.
  1. a="Bon"+"jour"
  2. b=2*"bon"
  3. c="2"+"3"
  4. d="2"*3
  1. >>> a="Bon"+"jour"
>>> a
'Bonjour'
>>> type(a)
<class 'str'>
  2. >>> b=2*"bon"
>>> b
'bonbon'
>>> type(b)
<class 'str'>
  3. >>> c="2"+"3"
>>> c
'23'
>>> type(c)
<class 'str'>
  4. >>> d="2"*3
>>> d
'222'
>>> type(d)
<class 'str'>
Booléens
Pour chacune des variables suivantes, indique sa valeur et son type.
  1. a=2==3
  2. b=2!=3
  3. c=2<3
  4. d=2>3
  5. e=2<=3
  6. f=2>=3
  7. g=2==2.0
  8. h=0.2+0.1==0.3
  9. i="2"*3==6
  10. j="2"*3=="2*3"
  11. k="2"*3==222
  12. l="2*3==6"
  1. >>> a=2==3
>>> a
False
>>> type(a)
<class 'bool'>
  2. >>> b=2!=3
>>> b
True
>>> type(b)
<class 'bool'>
  3. >>> c=2<3
>>> c
True
>>> type(c)
<class 'bool'>
  4. >>> d=2>3
>>> d
False
>>> type(d)
<class 'bool'>
  5. >>> e=2<=3
>>> e
True
>>> type(e)
<class 'bool'>
  6. >>> f=2>=3
>>> f
False
>>> type(f)
<class 'bool'>
  7. >>> g=2==2.0
>>> g
True
>>> type(g)
<class 'bool'>
  8. >>> h=0.2+0.1==0.3
>>> h
False
>>> type(h)
<class 'bool'>
  9. >>> i="2"*3==6
>>> i
False
>>> type(i)
<class 'bool'>
  10. >>> j="2"*3=="2*3"
>>> j
False
>>> type(j)
<class 'bool'>
  11. >>> k="2"*3==222
>>> k
False
>>> type(k)
<class 'bool'>
  12. >>> l="2*3==6"
>>> l
"2*3==6"
>>> type(l)
<class 'str'>

Les boucles

En Python, une boucle for i in range(n) répète un bloc d'instructions n fois. 
for i in range(n):
    Instruction 1
    Instruction 2
    ...
Instructions effectuées après la boucle
  1. Recopiez et complétez le tableau des valeurs de a et b au cours de l'exécution du programme ci-contre.
a,b = 0,1
for i in range(3):
    a=a+1
    b=b*a
ligne n° 1 2
i=0		 3
i=0		 4
i=0		 2
i=1		 3
i=1		 4
i=1		 2
i=2		 3
i=2		 4
i=2
a ... ... ... ... ... ... ... ... ... ...
b ... ... ... ... ... ... ... ... ... ...
  1. On remplace range(3) par range(4), quelles sont les valeurs de a et b à la fin du script ?
  2. On inverse les lignes 3 et 4 du programme, que se passe-t-il ?
  3. Le programme ci-contre donne-t-il le même résultat pour b ? Justifiez.
    b=1
for i in range(4):
    b=b*(i+1)
  1. ligne n° 1 2
    i=0    		 3
    i=0    		 4
    i=0    		 2
    i=1    		 3
    i=1    		 4
    i=1    		 2
    i=2    		 3
    i=2    		 4
    i=2
    a 0 0 1 1 1 2 2 2 3 3
    b 1 1 1 1 1 1 2 2 2 6 
  2. a,b = 0,1
for i in range(4):
    a=a+1
    b=b*a
    ligne n° 1 2
    i=0    		 3
    i=0    		 4
    i=0    		 2
    i=1    		 3
    i=1    		 4
    i=1    		 2
    i=2    		 3
    i=2    		 4
    i=2    		 2
    i=3    		 3
    i=3    		 4
    i=3
    a 0 0 1 1 1 2 2 2 3 3 3 4 4
    b 1 1 1 1 1 1 2 2 2 6 6 6 24 
  3. a,b = 0,1
for i in range(4):
    b=b*a
    a=a+1
    ligne n° 1 2
    i=0    		 3
    i=0    		 4
    i=0    		 2
    i=1    		 3
    i=1    		 4
    i=1    		 2
    i=2    		 3
    i=2    		 4
    i=2    		 2
    i=3    		 3
    i=3    		 4
    i=3
    a 0 0 0 1 1 1 2 2 2 3 3 3 4
    b 1 1 0 0 0 0 0 0 0 0 0 0 0

    On remarque que la valeur finale de a reste inchangée mais que la valeur de b est nulle.

  4. b=1
for i in range(4):
    b=b*(i+1)
    ligne n° 1 2
    i=0    		 3
    i=0    		 2
    i=1    		 3
    i=1    		 2
    i=2    		 3
    i=2    		 2
    i=3    		 3
    i=3
    b 1 1 1 1 2 2 6 6 24

    La variable b prend les mêmes valeurs que dans le premier programme car a et i+1 sont équivalents.

En Python, une boucle while condition répète un bloc d'instructions tant qu'une condition est vraie. 
while condition:
    Instruction 1
    Instruction 2
    ...
Instructions effectuées après la boucle
On reprend l'algorithme précédent mais on remplace la boucle for par une boucle while pour déterminer le seuil de a à partir duquel b dépasse $\num{1000000}$.
  1. Construisez et complétez le tableau des valeurs de a et b au cours de l'exécution du programme ci-contre.
a,b = 0,1
while b<=1000000:
    a=a+1
    b=b*a
  1. Quel est le seuil pour dépasser $10^6$ ?
  2. Quel est le seuil pour dépasser $10^9$ ?
  1. ligne n° 1 2 3 4 2 3 4 2 3 4 2 3 4 2
    a 0 0 1 1 1 2 2 2 3 3 3 4 4 4
    b 1 1 1 1 1 1 2 2 2 6 6 6 24 24
    ligne n° 3 4 2 3 4 2 3 4 2 3
    a 5 5 5 6 6 6 7 7 7 8
    b 24 120 120 120 720 720 720 5040 5040 5040
    ligne n° 4 2 3 4 2 3 4 2
    a 8 8 9 9 9 10 10 10
    b 40320 40320 40320 362880 362880 362880 3628800 3628800

    Le seuil pour dépasser $10^6$ est $10$.

  2. Le seuil pour dépasser $10^9$ est $13$.